package solution._0030._0033;

/**
 * Created by chen_snow
 * Date: 2021/5/19 23:04
 * Description: 搜索旋转排序数组
 */
public class Solution {

    public static void main(String[] args) {
        int[] data = {4,5,6,7,0,1,2};
        search(data, 3);
    }

    public static int search(int[] nums, int target) {
        return searchIndex(nums, target, 0, nums.length - 1);
    }

    public static int searchIndex(int[] nums, int target, int start, int end) {

        int middle = (end - start) / 2 + start;
        if (nums[middle] == target) {
            return middle;
        }

        if (start >= end) {
            return -1;
        }

        if (nums[middle] >= nums[0]) {
            if ( nums[start] <= target && target < nums[middle] ) {
                return searchIndex(nums, target, start, middle - 1);
            } else {
                return searchIndex(nums, target, middle + 1, end);
            }
        } else {
            if (nums[middle] < target && target <= nums[end]) {
                return searchIndex(nums, target, middle + 1, end);
            } else {
                return searchIndex(nums, target, start, middle - 1);
            }
        }

    }

}
